public class Sort {
    /**
     * 归并排序-》
     * 时间复杂度：O(N*logN) 每一层递归区间加起来为N, 树的高度为以2为底的logN, 因此时间复杂度为O(N*logN)
     * 空间复杂度：O(logN) 空间复杂度实际就是树的高度
     * 稳定性：稳定的排序
     * 目前为止3个稳定的排序：直接插入排序、冒泡排序、归并排序
     */
    public static void mergeSort(int[] array) {
        mergeSortFun(array,0,array.length-1);
    }

    private static void mergeSortFun(int[] array, int start, int end) {
        //start >= end说明左边递归完了右边递归完了,左右相遇
        if (start >= end) {
            return;
        }
        //分解
        int mid = (start+end)/2;
        //左区间递归
        mergeSortFun(array,start,mid);
        //右区间递归
        mergeSortFun(array,mid+1,end);
        //通过merge方法合并数组array,要有范围,即要知道开始位置start,结束位置end,中间位置mid
        merge(array,start,mid,end);
    }

    private static void merge(int[] array, int left, int mid, int right) {
        //可以不定义s1, s2, e1, e2, 直接用start, end, mid
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;
        //定义一个新的数组
        int[] tmpArr = new int[right-left+1];
        int k = 0; //tmArr数组的下标
        //同时满足两个归并数组都有数据
        while (s1 <= e1 && s2 <= e2) {
            if (array[s1] <= array[s2]) {
                tmpArr[k++] = array[s1++];
            }else {
                tmpArr[k++] = array[s2++];
            }
        }
        //有可能一段走完后另一段存在多个数据, 因此用while而不用if
        while (s1 <= e1) {
            tmpArr[k++] = array[s1++];
        }
        while (s2 <= e2) {
            tmpArr[k++] = array[s2++];
        }
        //把排好序的数据拷贝回原来的数组array当中, 因为还有右边排好的也要拷贝, 因此下标加上left
        for (int i = 0; i < tmpArr.length; i++) {
            array[i+left] = tmpArr[i];
        }
    }

    /**
     * 非递归实现归并排序
     */
    public static void mergeSortNor(int[] array) {
        int gap = 1; //每组几个数据
        while (gap < array.length) {
            for (int i = 0; i < array.length; i+=2*gap) {
                int left = i;
                int mid = left+gap-1; //可能会越界
                int right = mid+gap; //可能会越界
                //越界则指向数组最后一个数
                if (mid >= array.length) {
                    mid = array.length-1;
                }
                if (right >= array.length) {
                    right = array.length-1;
                }
                merge(array,left,mid,right);
            }
            //1个有序1个有序走完了到2个2个有序到4个4个有序...
            gap *= 2;
        }
    }

    /**
     * 计数排序的场景：
     * 指定范围内的数据
     * 时间复杂度：O(MAX(N+范围))
     * 空间复杂度：O(范围)
     * 稳定性：稳定的排序(目前所写代码不稳定)
     */
    public static void countSort(int[] array) {
        //求数组的最大最小值 O(N)
        int minVal = array[0];
        int maxVal = array[0];
        for (int i = 0; i < array.length; i++) {
            if (minVal > array[i]) {
                minVal = array[i];
            }
            if (maxVal < array[i]) {
                maxVal = array[i];
            }
        }
        //确定计数组的长度
        int len = maxVal - minVal + 1;
        int[] count = new int [len];
        //遍历array数组 把数据出现的次数储存到计数数组当中 O(N)
        for (int i = 0; i < array.length; i++) {
            count[array[i]-minVal]++;
        }
        //计数数组已经存放了每个数据出现的次数
        //遍历计数数组 把实际的数据写回array数组 O(范围) count的长度和最大最小值有关系
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                //这里需要重写回array 意味着得从array的0位置开始写
                array[index] = i+minVal;
                index++;
                count[i]--;
            }
        }
    }
}
